package nachos.vm;

import nachos.machine.*;
import nachos.threads.*;
import nachos.userprog.*;
import nachos.vm.*;

import java.util.Random;

/**
 * A <tt>UserProcess</tt> that supports demand-paging.
 */
public class VMProcess extends UserProcess {
	private static final Lock clockLock = new Lock();
	private static int hand = 0;
	private static final int pageSize = Processor.pageSize;
	private static final Random random = new Random();
	private int[] swapTable;

	/**
	 * Initializes page tables for this process so that the executable can be
	 * demand-paged.
	 * 
	 * @return <tt>true</tt> if successful.
	 */
	protected boolean loadSections() {

		// Initialize the swap table to be invalid.
		// Initialize the page table to be invalid.
		swapTable = new int[numPages];
		pageTable = new TranslationEntry[numPages];
		for (int i = 0; i < numPages; i++) {
			pageTable[i] = new TranslationEntry();
			swapTable[i] = -1;
		}

		return true;
	}

	/**
	 * Release any resources allocated by <tt>loadSections()</tt>.
	 */
	protected void unloadSections() {
		for (int i = 0; i < Machine.processor().getTLBSize();i++) {
			TranslationEntry entry = Machine.processor().readTLBEntry(i);
			if (entry.valid) {
				entry.valid = false;
				Machine.processor().writeTLBEntry(i,entry);
			}
		}
		for (int vpn=0; vpn<pageTable.length; vpn++)
			if (pageTable[vpn].valid) {
				VMKernel.invertedPageTable[pageTable[vpn].ppn] = null;
				VMKernel.freePages.add(new Integer(pageTable[vpn].ppn));
			}
			else if (swapTable[vpn] != -1) {
				VMKernel.freeSwapPages.add(new Integer(swapTable[vpn]));
			}

	}

	/**
	 * Allocate a new process.
	 */
	public VMProcess() {
		super();
	}

	/**
	 * Save the state of this process in preparation for a context switch.
	 * Called by <tt>UThread.saveState()</tt>.
	 */
	public void saveState() {
		super.saveState();
		for (int i = 0; i < Machine.processor().getTLBSize(); i++) {
			TranslationEntry entry = Machine.processor().readTLBEntry(i);
			if (entry.valid) {
				pageTable[entry.vpn].dirty = entry.dirty;
				pageTable[entry.vpn].used = entry.used;
				entry.valid = false;
				Machine.processor().writeTLBEntry(i, entry);
			}
		}
	}

	/**
	 * Restore the state of this process after a context switch. Called by
	 * <tt>UThread.restoreState()</tt>.
	 */
	public void restoreState() {
		// super.restoreState();
	}

	/**
	 * Handle a user exception. Called by <tt>UserKernel.exceptionHandler()</tt>
	 * . The <i>cause</i> argument identifies which exception occurred; see the
	 * <tt>Processor.exceptionZZZ</tt> constants.
	 * 
	 * @param cause
	 *            the user exception that occurred.
	 */
	public void handleException(int cause) {

		switch (cause) {
		case (Processor.exceptionTLBMiss): {
			handleTLBMiss();
			break;
		}
		default:
			super.handleException(cause);
			break;
		}
	}

	private void handleTLBMiss() {

		int badAddr = Machine.processor().readRegister(Processor.regBadVAddr);
		int vpn = Processor.pageFromAddress(badAddr);

		handleTLBMiss(vpn);
	}
	

	private void handleTLBMiss(int vpn) {

		Processor processor = Machine.processor();
		// Stores the id of the translation entry that will be replaced
		int freeEntry = -1;
		for (int i = 0; (i < Machine.processor().getTLBSize())
				&& (freeEntry == -1); i++) {
			TranslationEntry entry = Machine.processor().readTLBEntry(i);
			
			if (!entry.valid)
				freeEntry = i;
		}
		// if no free entry was found, replace at random;
		if (freeEntry == -1)
			freeEntry = random.nextInt(Machine.processor().getTLBSize());

		TranslationEntry old = Machine.processor().readTLBEntry(freeEntry);

		// If the entry is invalid, then we can just over write it.
		// If the entry is valid, then more checking must be done.
		if (old.valid) {
			pageTable[old.vpn].dirty = old.dirty;
			pageTable[old.vpn].used = old.used;
		}

		TranslationEntry newEntry = new TranslationEntry(pageTable[vpn]);
		while (!newEntry.valid) {
			handlePageFault(vpn);
			newEntry = new TranslationEntry(pageTable[vpn]);
		}
		Machine.processor().writeTLBEntry(freeEntry, newEntry);
	}

	private void handlePageFault(int faultingPageNum) {
		TranslationEntry faultingPage = pageTable[faultingPageNum];
		int ppn = getPPN();

		// Update translation entry
		faultingPage.valid = true;
		faultingPage.dirty = false;
		faultingPage.vpn = faultingPageNum;
		faultingPage.ppn = ppn;
		VMKernel.invertedPageTable[ppn] = this;

		int vpn = faultingPage.vpn;
		// find what section the vpn is in
		for (int s = 0; s < coff.getNumSections(); s++) {
			CoffSection section = coff.getSection(s);
			// keep going until right secion is found
			if (vpn >= section.getFirstVPN() + section.getLength())
				continue;


			// If section is not in swap, read from coff
			if (swapTable[vpn] == -1) {
				pageTable[vpn].readOnly = section.isReadOnly();
				// find what page of the section must be loaded in.
				int i = vpn - section.getFirstVPN();
				section.loadPage(i, ppn);
				// We're done!
				VMKernel.pinTable[ppn].release();
				return;
			} else {
				// Read only should never be in swap!
				Lib.assertTrue(!pageTable[vpn].readOnly);
				// treat the same as other pages when in swap.
				break;
			}
		}
		// if stack or argument not used yet, then start with it blank.
		if (swapTable[vpn] == -1) {
			byte[] page = new byte[Processor.pageSize];
			byte[] memory = Machine.processor().getMemory();

			System.arraycopy(page,0,memory,ppn*Processor.pageSize,page.length);
			// We're done!
			VMKernel.pinTable[ppn].release();
			return;
		}

		// it must be in swap.
		int spn = swapTable[vpn];
		byte[] page = new byte[Processor.pageSize];
		byte[] memory = Machine.processor().getMemory();
		VMKernel.swapFileRead(spn, page);
		System.arraycopy(page,0,memory,ppn*Processor.pageSize,page.length);
		// We're done!
		VMKernel.pinTable[ppn].release();

	}

	protected int pinVirtualPage(int vpn, boolean isUserWrite) {

    	if (vpn < 0 || vpn >= pageTable.length)
    	    return -1;
    	
	TranslationEntry entry = pageTable[vpn];

	VMKernel.pinTable[entry.ppn].acquire();

    	if(!entry.valid || entry.vpn != vpn) {
		VMKernel.pinTable[entry.ppn].release();
		handlePageFault(vpn);
    		return pinVirtualPage(vpn, isUserWrite);
	}
    	
    	if (isUserWrite) {
    	    if (entry.readOnly)
    		return -1;
    	    
	    for (int i = 0;i < Machine.processor().getTLBSize();i++) {
		TranslationEntry tlb_entry = Machine.processor().readTLBEntry(i);
		if (tlb_entry.valid && (tlb_entry.vpn == vpn) && 
			(VMKernel.invertedPageTable[tlb_entry.ppn] == this)) {
		    tlb_entry.dirty = true;
		    Machine.processor().writeTLBEntry(i,tlb_entry);
		}
	    }

	    entry.dirty = true;
    	}

	for (int i = 0; i < Machine.processor().getTLBSize();i++) {
	    TranslationEntry tlb_entry = Machine.processor().readTLBEntry(i);
	    if (tlb_entry.valid && (tlb_entry.vpn == vpn) &&
		    (VMKernel.invertedPageTable[tlb_entry.ppn] == this)) {
		tlb_entry.used = true;
		Machine.processor().writeTLBEntry(i,tlb_entry);
	    }
	}

    	entry.used = true;


    	
    	return entry.ppn;
        }

	protected void unpinVirtualPage(int vpn) {
		TranslationEntry entry = pageTable[vpn];
		VMKernel.pinTable[entry.ppn].release();
	}

	private int getPPN() {

		int ppn = -1;

		if (VMKernel.freePages.size() != 0) {
			ppn = (Integer) VMKernel.freePages.removeFirst();
			VMKernel.pinTable[ppn].acquire();
			return ppn;
		}

		// We will find the victim page that will be removed.
		TranslationEntry victim = null;

		for (int i = 0;i < Machine.processor().getTLBSize();i++) {
			TranslationEntry tlb_entry = Machine.processor().readTLBEntry(i);
			if (tlb_entry.valid && (tlb_entry.vpn == pageTable[tlb_entry.vpn].vpn)) {
				VMKernel.invertedPageTable[tlb_entry.ppn].pageTable[tlb_entry.vpn].dirty = tlb_entry.dirty;
				VMKernel.invertedPageTable[tlb_entry.ppn].pageTable[tlb_entry.vpn].used = tlb_entry.used;
			}
		}

		// do clock algorithm
		do {

			clockLock.acquire();
			int myHand = hand;

			VMProcess process = VMKernel.invertedPageTable[myHand];
			// find translation entry of the page that is a potential victim

			if (process == null) {
				clockLock.release();
				return getPPN();
			}

			hand++;
			if (hand == Machine.processor().getNumPhysPages())
				hand = 0; 

			clockLock.release();

			TranslationEntry potVictim = null;
			
			for (TranslationEntry entry : process.pageTable) {
				if (entry.valid && entry.ppn == myHand) {
					potVictim = entry;
					break;
				}
			}

			if (potVictim == null)
				return getPPN();

			int possiblePPN = potVictim.ppn;
			VMKernel.pinTable[possiblePPN].acquire();

			if (process != VMKernel.invertedPageTable[possiblePPN]
				||!potVictim.valid || potVictim.ppn != possiblePPN)
			{
				VMKernel.pinTable[possiblePPN].release();
				return getPPN();
			}

			if (potVictim.used == false) {
				ppn = potVictim.ppn;
				victim = potVictim;
			} else
				potVictim.used = false;

			if (ppn == -1)
				VMKernel.pinTable[possiblePPN].release();
			else if (ppn != possiblePPN)
				// Should never happen...
				Lib.assertNotReached();

		} while (ppn == -1);

		// If the page being evicted is clean, just remove it.
		if (!victim.dirty) {
			victim.valid = false;
			for (int i = 0;i < Machine.processor().getTLBSize();i++) {
				TranslationEntry entry = Machine.processor().readTLBEntry(i);
				if (entry.valid && (entry.ppn == ppn)) {
					entry.valid = false;
					Machine.processor().writeTLBEntry(i,entry);
					break;
				}
			}
			return ppn;
		}

		// else we must write the page to swap space.
		byte[] page = new byte[Processor.pageSize];
		byte[] memory = Machine.processor().getMemory();
		System.arraycopy(memory,ppn*Processor.pageSize,page,0,page.length);


		// find the swap page number.
		int spn = -1;
		if (VMKernel.invertedPageTable[ppn].swapTable[victim.vpn] != -1)
			spn = VMKernel.invertedPageTable[ppn].swapTable[victim.vpn];
		else if (VMKernel.freeSwapPages.isEmpty()) {
			spn = VMKernel.nextSwapPage++;
		} else
			spn = (Integer) VMKernel.freeSwapPages.remove(0);

		VMKernel.swapFileWrite(spn, page);

		victim.valid = false;
		VMKernel.invertedPageTable[ppn].swapTable[victim.vpn] = spn;

		return ppn;
	}

	private static final char dbgProcess = 'a';
	private static final char dbgVM = 'v';
}
